package 剑指offer;

public class 剑指Offer63股票的最大利润 {
    //动规
    public int maxProfit(int[] prices) {
        if(prices.length < 1) return 0;
        int max = 0;
        int min = prices[0];
        for(int i = 0 ;i < prices.length;i++){
            max = Math.max(max,prices[i] - min);
            min = Math.min(min,prices[i]);
        }
        return max;
    }
    //暴力循环
    public int maxProfit1(int[] prices) {
        int maxVal = 0;//len = 6,i < 6-1 -> i 最大取6-2 = 4;j = i+1;j 最小取1；最大取len- 1
        for(int i = 0;i < prices.length-1 ;i++){
            for(int j = i + 1;j < prices.length;j++){
                maxVal = maxVal > (prices[j] - prices[i]) ? maxVal : prices[j] - prices[i];
            }
        }
        return maxVal;
    }
    public int maxProfit3(int[] prices) {
        if(prices.length < 2) return 0;
        int index = 0;
        int min = prices[0];
        int max = 0;
        for(int i = 0;i < prices.length; i++){
            if(min < prices[i]){
                index = i;
                min = prices[i];
            }
        }
        if(index == prices.length - 1) return 0;
        for(int i = index;i < prices.length ;i++){
            max = Math.max(max,prices[i]);
        }
        return max - min;
    }

    //暴力递归
    public int maxProfit2(int[] prices) {
        if(prices.length < 2){
            return 0;
        }
        //否存在两个以上得数
        return help(prices,0);
    }
    private int help(int[] arr,int index){
        if(index == arr.length-1){
            return 0;
        }
        int buy = arr[index];
        int sale = 0;
        for(int i = index + 1;i < arr.length;i++){
            sale = sale > arr[i] ? sale : arr[i];
        }
        int max = Math.max((sale - buy),help(arr,index+1));
        return max > 0 ? max : 0;

    }
}
